package my.jwds.p145;

import my.jwds.p94.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostorderTraversal {


    public static void main(String[] args) {
        PostorderTraversal o = new PostorderTraversal();
        TreeNode node = TreeNode.to_binary(new int[]{1,2,3,4,5,6,7});
        System.out.println(o.postorderTraversal(node));
    }


    public List<Integer> postorderTraversal_1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        Stack<TreeNode> stackLeft = new Stack<>();
        Stack<TreeNode> stackRight = new Stack<>();
        while(!stack.empty()){
            TreeNode node = stack.pop();
            TreeNode prevLeft = stackLeft.empty() ? null : stackLeft.pop();
            if ( node.left != prevLeft && node != prevLeft){
                while(node != null){
                    stack.push(node);
                    stackLeft.push(node);
                    node = node.left;

                }
                node = stack.pop();
            }
            TreeNode prevRight = stackRight.empty() ? null : stackRight.pop();
            if (node.right != prevRight && node != prevRight){
                while(node != null){
                    stack.push(node);
                    stackRight.push(node);
                    node = node.right;
                }
                node = stack.pop();

            }
            res.add(node.val);
        }
        return res;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root != null){
            if (root.left != null){
                res.addAll(postorderTraversal(root.left));
            }
            if (root.right != null){
                res.addAll(postorderTraversal(root.right));
            }
            res.add(root.val);
        }
        return res;
    }
}
